Codes on graphs have become a topic of great current interest in the coding the-ory community. The prime examples of codes on graphs are low-density parity-check (LDPC) codes that have been widely considered as next-generation error-correcting codes for many real world applications in digital communication and magnetic storage. However, because of their distinct properties, LDPC codes decoder/encoder design and implementation are not trivial and design of these codes stills remain a challenging task. How well one attacks this problem directly determines the extent of LDPC application in the real world. As a class of LDPC codes, (3,k)-regular LDPC codes can achieve very good performance and hence are considered in this invention.
The main challenge when implementing the message passing algorithm for decoding LDPC codes is managing the passing of the messages. The realization of the message passing bandwidth results in very different and difficult challenges depending on whether all the messages are passed in fully parallel or partly parallel manner. By fully exploiting the parallelism of the message passing decoding algorithm, a fully parallel decoder can achieve very high decoding throughput but suffers from prohibitive implementation complexity (see, e.g., A. J. Blanksby and C. J. Howland, “A 690-mW 1-Gb/s 1024-b, rate-½ low-density parity-check code decoder”, IEEE Journal of Solid-State Circuits, vol. 37, pp. 404–412 (March, 2002)). Furthermore, the large number of interconnection may limit the speed performance and increase the power dissipation. Thus the fully parallel design strategy is only suitable to short code length scenarios.
In partly parallel decoding, the computations associated with a certain number of variable nodes or check nodes are time-multiplexed to a single processor. Meanwhile, since the computation associated with each node is not complicated, the fully parallel interconnection network should be correspondingly transformed to partly parallel ones to achieve both the communication complexity reduction and high-speed partly parallel decoding. Unfortunately, the randomness of the Tanner graph makes it nearly impossible to develop such a transformation. In other words, an arbitrary random LDPC code has little chance to be suited for high-speed partly parallel decoder hardware implementation.
Furthermore, to perform LDPC encoding, the generator matrix is typically used, which has quadratic complexity in the block length. How to reduce the encoding complexity for the practical coding system implementation is another crucial issue.
What is needed is new joint code-encoder-decoder design methodology and techniques for designing practical LDPC coding system, that overcomes the limitations of the conventional code first scheme and/or designs.